1. Field
The disclosure relates generally to processing instructions and more specifically to predicting instructions that will be needed by a processor unit following processing of a conditional instruction. Still more specifically, the present disclosure relates to control flow and predicting branches of a program that will be used.
2. Description of the Related Art
A program is a sequence of instructions for a process that performs certain tasks when processed by a processor unit. The speed with which the program is able to perform the tasks is often dependent on the efficiency of the processor unit. When an instruction is needed by the processor unit, the processor unit retrieves the instruction from a cache of the processor unit. If the instruction needed by the processor unit is not present in the cache, the instruction can be retrieved from another storage device, such as memory, for example. Retrieving instructions from memory can take a longer amount of time than retrieving instructions from a cache. The processor unit may have to wait while the instruction is retrieved. As a result, the performance of the program may slow down.
Computer systems often use different forms of instruction prediction to speed up the performance of a program. For example, most recently used instructions from a program may be kept in the cache for use by the processor unit. In another example, instructions that are commonly processed in a sequence may be placed in the cache in the order of the sequence. However, caches have limited sizes. Thus, only a limited number of instructions may be stored in the cache for processing by the processor. Prediction of the correct instructions is important because incorrectly predicted instructions waste space in the cache, the processor pipeline, and processing cycles. A “number”, as used herein with reference to an item, means one or more items.
Depending on the task being performed, instructions from the program may be needed in any number of different sequences. For example, processing of a conditional instruction may result in two different possible sequences being needed. A conditional instruction is an instruction that, when processed, results in one of at least two different instructions being needed by the processor unit next. For example, a conditional instruction may contain an “if-then” statement. If the condition in the “if” statement is true, “then” the program will follow one set of instructions, otherwise the program may follow a different set of instructions. A “set”, as used herein with reference to an item, means one or more items.
To improve efficiency, many processor units use an instruction pipeline. Use of an instruction pipeline is a technique that allows the processor unit to process different stages of more than one instruction at the same time. Processing of a single instruction can require more than one step performed by the processor. For example, processing of an instruction may include four stages. Rather than waiting until processing of an instruction is complete, the processor unit can begin processing stages of other instructions. As a result, the processor unit may be able to finish processing one instruction each cycle.
Another performance technique is to prefetch the pipeline with an upcoming instruction set. For example, a branch in the program, due to a conditional statement, may result in one of at least two sets of instructions being chosen to be loaded into the pipeline. However, incorrectly predicting the result of instructions needed following a conditional instruction can be costly. If the instructions needed following the conditional instruction are incorrectly predicted, any processing of the incorrectly predicted instructions is wasted. The instruction pipeline will need to be flushed. The processor unit will then need to fetch the correct instruction set needed following the conditional instruction. Both of these steps waste processor unit cycles and reduce the efficiency of the processor unit.
Accordingly, it would be advantageous to have a method and apparatus which take into account one or more of the issues discussed above as well as possibly other issues.